В данном задании вам необходимо самостоятельно реализовать один из алгоритмов кластеризации.
По аналогии с классами в scikit-learn, нужно реализовать класс, наследуемый от Base Estimator.
Подробнее про реализацию своих моделей в scikit-learn: here.
В классе помимо __init__() нужно реализовать два метода:
fit() - метод, выполняющий кластеризацию данных.predict() - метод, определяющий для нового объекта, к какому из кластеров он относится. Для удобства можно создавать дополнительные методы класса, которые будут вызываться в fit() или predict().
Функции для вычисления расстояний между объектами самим реализовывать не нужно, используйте реализации из scipy.
# Не до конца получилось реализовать на момент отправления работы
import numpy as np
from scipy.spatial import distance
from sklearn.base import BaseEstimator, ClusterMixin
class My_Clust(BaseEstimator, ClusterMixin):
"""
My implementation of clustering algorithm
"""
def __init__(self, n_clusters=8, init='k-means++', n_init=10, max_iter=500, tol=0.0001):
self.inertia_ = 0
self.cluster_centers_ = list()
self.labels_ = list()
self.X_ = None
self.y_ = None
self.size_ = 0
self.n_clusters = n_clusters
self.init = init
self.n_init = n_init
self.max_iter = max_iter
self.tol = tol
def get_labels(self):
return self.labels_
def get_params(self, deep=True):
return {
"n_clusters": self.n_clusters,
"init": self.init,
"n_init": self.n_init,
"max_iter": self.max_iter,
"tol": self.tol,
}
def set_params(self, **params):
for parameter, value in params.items():
setattr(self, parameter, value)
return self
def fit(self, X, y=None):
self.X_ = np.array(X)
self.size_ = len(self.X_)
solutions_list = list()
n, p = X.shape
for i in range(self.n_init):
self.cluster_centers_ = list()
self.labels_ = [0 for i in range(self.size_)]
centers = np.random.choice(n, size=self.n_clusters, replace=False)
centers = X[centers, :]
center_buf = centers
center_buf_2 = centers
clusters_result = []
distances = np.zeros((n, self.n_clusters))
for loop in range(self.max_iter):
center_buf_2 = center_buf
for i in range(n):
for j in range(self.n_clusters):
distances[i, j] = distance.euclidean(X[i], center_buf[j])
clusters_result = np.argmin(distances, 1)
for i in range(self.n_clusters):
check = False
for j in range(n):
if (clusters_result[j] == i):
check = True
if (check):
center_buf[i] = np.mean(X[clusters_result == i], 0)
self.labels_ = clusters_result
return self
my_kmeans = My_Clust(n_clusters=3, init='k-means++')
my_kmeans.fit(iris.data)
Алгоритм K-Means.
Параметры:
Атрибуты:
Метод predict(): Новый объект определяется в кластер, центр которого расположен ближе всех к этому объекту.
Вашу реализацию необходимо сравнить с питоновской реализацией алгоритма из sklearn или scipy. Результаты кластеризации должны совпадать.
Также необходимо сравнить скорость работы вашей реализации и питоновской (это нормально, если ваша реализация будет медленнее).
Сравнение необходимо выполнить на наборе данных iris.
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
import seaborn as sns
iris = load_iris()
X = iris.data # использовать для кластеризации
y = iris.target # истинные метки цветков
X = pd.DataFrame(X, columns=iris.feature_names)
X['class'] = [iris.target_names[i] for i in y]
sns.pairplot(X, hue='class', plot_kws={'alpha':0.5}, vars=iris.feature_names)
plt.show()
Дополнительно вы можете поработать над эффективностью алгоритма по скорости и памяти, добавить поддержку многопоточности, или расширить базовый функционал.
import time
iris_p = iris.data.copy()
my_kmeans = My_Clust(n_clusters=3, init='k-means++')
start_time = time.clock()
my_kmeans.fit(iris_p)
my_time = time.clock() - start_time
labels = my_kmeans.get_labels()
iris_p['class'] = labels
sns.pairplot(iris_p, hue='class', plot_kws={'alpha': 0.75}, vars=iris.feature_names)
plt.show()
В данном задании вам предлагается проанализировать набор данных по различным городам США. Каждый город характеризуется следующими признаками:
pd.set_option('display.max_colwidth', None)
data_desc = pd.read_csv('Data_Description.txt', sep=':')
data_desc
Housing и Crime - наоборот.Population- статистический признак, не имеющий интерпретации как “лучше-хуже”.Place - уникальный идентификатор объекта (города), он не должен использоваться при кластеризации.Longitude и Latitude. Их также не следует использовать при кластеризации данных.import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import scipy.cluster.hierarchy as h
data = pd.read_csv('Data.txt', sep=' ')
data
# Стандартизация данных
from sklearn.preprocessing import MinMaxScaler
minmax = MinMaxScaler()
data_updated = data[['Climate', 'HousingCost', 'HlthCare', 'Crime', 'Transp' , 'Educ', 'Arts', 'Recreat', 'Econ', 'Pop']]
data_transformed = minmax.fit_transform(data_updated)
data_scaled = pd.DataFrame(data_transformed, columns=data_updated.columns)
data_scaled
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
plt.figure(figsize=(50, 25))
h.dendrogram(Z, p=50)
plt.show()
from sklearn.metrics import silhouette_score
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
labels_h = h.fcluster(Z, t=3, criterion='maxclust')
print('metric:' + m)
print(silhouette_score(data_scaled, labels_h), '\n')
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
labels_h = h.fcluster(Z, t=4, criterion='maxclust')
print('metric:' + m)
print(silhouette_score(data_scaled, labels_h), '\n')
for m in ['euclidean', 'minkowski', 'cityblock']:
Z = h.linkage(data_scaled, metric=m, method='complete')
labels_h = h.fcluster(Z, t=5, criterion='maxclust')
print('metric:' + m)
print(silhouette_score(data_scaled, labels_h), '\n')
Сityblock выдал результат лучше при 3-4 кластерах, в то время как при 5 кластерах euclidean & minkowski были лучше. Сейчас и далее эффективность я буду оценивать метрикой silhouette_score
# Рассмотрим различные расстояниям между кластерами
for M in ['single', 'complete', 'average', 'weighted', 'centroid', 'median', 'ward']:
Z = h.linkage(data_scaled, metric='euclidean', method=M)
plt.figure(figsize=(15,10))
plt.title(M)
_=h.dendrogram(Z, p=50, truncate_mode='lastp')
for M in ['single', 'complete', 'average', 'weighted', 'centroid', 'median', 'ward']:
max_score = 0
clusters_num = 0
for N in range(3, 10):
Z = h.linkage(data_scaled, method=M)
labels_h = h.fcluster(Z, t=N, criterion='maxclust')
initial = silhouette_score(data_scaled, labels_h)
if initial > max_score:
max_score = initial
clusters_num = N
print('method:' + M + '\nclusters number:', clusters_num, '\nSilhouette score:', max_score, '\n')
for M in ['single', 'complete', 'average', 'weighted']:
max_score = 0
clusters_num = 0
for N in range(3, 10):
Z = h.linkage(data_scaled, metric='cityblock', method=M)
labels_h = h.fcluster(Z, t=N, criterion='maxclust')
initial = silhouette_score(data_scaled, labels_h)
if initial > max_score:
max_score = initial
clusters_num = N
print('method:' + M + '\nclusters number:', clusters_num, '\nSilhouette score:', max_score, '\n')
Лучше всего себя показали методы single и median с количеством кластеров - 3 и метрикой euclidean. Такой же результат был у single с кол-вом кластеров - 3 и метрикой cityblock.
import warnings
warnings.filterwarnings('ignore')
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='single', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='median', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='single', metric='cityblock')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Несмотря на неплохой результат silhouette_score, результат вышел плохим. Существует один большой кластер, а остальные кластеры - отдельные точки. Поэтому необходимо перебрать другие вариант, которые, возможно, показали себя не так хорошо по результатам метрики.
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='complete', metric='cityblock')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='weighted', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
data_pred = data_scaled.copy()
h_cluster = h.linkage(data_pred, method='centroid', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
h_cluster = h.linkage(data_pred, method='ward', metric='euclidean')
labels = h.fcluster(h_cluster, t=3, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Визуально method='ward' и metric='euclidean' выглядят гораздо лучше, видно не один большой кластер, а несколько. Проверим еще другое кол-во кластеров.
h_cluster = h.linkage(data_pred, method='ward', metric='euclidean')
labels = h.fcluster(h_cluster, t=4, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
h_cluster = h.linkage(data_pred, method='ward', metric='euclidean')
labels = h.fcluster(h_cluster, t=5, criterion='maxclust')
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
По итогу я склоняюсь к 4 кластерам, мне кажется, это оптимальное кол-во.
from sklearn.cluster import DBSCAN
for E in np.arange(0.5, 3, 0.5):
for MS in range(3, 7):
db_cluster = DBSCAN(eps=E, min_samples=MS, metric='euclidean').fit(data_pred)
labels = db_cluster.labels_
print(E, MS, '\n', pd.Series(labels).value_counts(), '\n')
Наиболее подходящими кажутся значение 1.0 для eps и min_samples = 3.
db_cluster = DBSCAN(eps=1.0, min_samples=3, metric='euclidean').fit(data_pred)
labels = db_cluster.labels_
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Мне кажется, что 5 кластеров является оптимальным количеством.
from sklearn.cluster import KMeans
plt.figure(figsize=(15, 10))
inertia = []
# Определяем оптимальное кол-во кластеров
for i in range(2, 20):
kmeans = KMeans(n_clusters=i, n_init=10)
kmeans.fit(data_scaled)
labels = kmeans.predict(data_scaled)
inertia.append(kmeans.inertia_)
plt.plot(range(2, 20), inertia, 'x-r')
plt.show()
Мне показалось, что 7 кластеров подходят в данном случае лучше всего, но я решила еще раз удостовериться в последующих экспериментах.
kmeans = KMeans(n_clusters=7, n_init=10)
kmeans.fit(data_scaled)
labels_kmeans = kmeans.predict(data_scaled)
print(labels_kmeans)
[sum(labels_kmeans==x) for x in range(7)]
for N in range(4,8):
k_cluster = KMeans(n_clusters=N, init='k-means++', random_state=3).fit(data_pred)
labels = k_cluster.labels_
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
Мне показалось, что наиболее подходящими выглядят 5 и 7 кластеров, но я все равно оставлю предпочтение последнему.
from hdbscan import HDBSCAN, hdbscan
hdb_cluster = hdbscan.HDBSCAN(min_cluster_size=14, gen_min_span_tree=True)
hdb_cluster.fit(data_pred)
labels = hdb_cluster.labels_
data_pred['class'] = labels
sns.pairplot(data_pred, hue='class', plot_kws={'alpha': 0.75})
plt.show()
pd.Series(cl_hdbscan.labels_).value_counts()
pip install numpy --upgrade
# Silhouette_score
h_cluster = h.linkage(data_scaled, method='ward', metric='euclidean')
labels_h = h.fcluster(h_cluster, t=4, criterion='maxclust')
db_cluster = DBSCAN(eps=1.0, min_samples=3, metric='euclidean').fit(data_pred)
labels_db = db_cluster.labels_
k_cluster = KMeans(n_clusters=N, init='k-means++', random_state=3).fit(data_scaled)
labels_kmeans = k_cluster.labels_
silhouette_score(data_scaled, labels_h)
silhouette_score(data_scaled, labels_db)
silhouette_score(data_scaled, labels_kmeans)
from sklearn.metrics import calinski_harabasz_score
calinski_harabasz_score(data_scaled, labels_h)
calinski_harabasz_score(data_scaled, labels_db)
calinski_harabasz_score(data_scaled, labels_kmeans)
from sklearn.metrics import davies_bouldin_score
davies_bouldin_score(data_scaled, labels_h)
davies_bouldin_score(data_scaled, labels_db)
davies_bouldin_score(data_scaled, labels_kmeans)
Как мне показалось, наиболее подходящим разбиением вышло K-means
data_pred['class'] = labels_kmeans
data = [data.loc[data_pred['class'] == i] for i in range(7)]
data[0]
data[1]
data[2]
data[3]
data[4]
data[5]
data[6]
Показатель Educ не сильно отличается от класса к классу.
Средний HousingCost, большая Population, хорошо развит Transp
HousingCost ниже среднего, высокий Econ, низкий Arts, низкая Pop.
HousingCost ниже среднего, средний показатель HlthCare, низкий Crime, экономический показатель невысокий, низкий Arts, низкая Pop.
HousingCost самый дорогой, большая Population, низкий Crime, высокий Econ. Группа городов, которая очень хороша для проживания, несмотря на высокую цену жилья. Географически самые теплые страны.
HousingCost ниже среднего, экономический показатель невысокий
Cредний HousingCost, низкая Pop.
Высокая HousingCost, высокий показатель HlthCare (выше, чем у остальных групп), впрочем, как и большинство показателей (Crime, Transp, Educ, Arts (очень сильно отличается от остальных)). Pop гораздо больше остальных, что говрит нам о том, что в данной группе наиболее большие города Америки.
pip install folium
import folium
colors = {
0: "green",
1: "pink",
2: "blue",
3: "orange",
4: "purple",
5: 'lightgreen',
6: "red"
}
_map = folium.Map(location=[39.091431, -96.655998], zoom_start=4)
for i in range(len(data)):
for index, city in data[i].iterrows():
folium.Marker(
location=[city["Lat"], city["Long"]],
icon=folium.Icon(color=colors[i]),
).add_to(_map)
_map
Действительно, зеленый кластер (0) - это достаточно крупные города (иногда даже столицы) в разных штатах (Вирджинии, Кентукки и других). Розовый (1), как и следовала ожидать, содержит города Америки, которые вряд ли кто-то знает (они небольшие). 2 кластер, голубой, сход с первым. Города третьего кластера (оранжевый) могут быть на слуху, они находятся преимущественно на побережьях, что делает цены на жилье высокими. Кластер 4, здесь можно встретить знакомые названия городов, но до сих пор это не самые развитые города. Как первый и второй кластеры преимущественно находится в центральной части Америки. Светло-зеленый кластер (5) географически находится на побережье страны, но не в таких дорогих местах, как 3 кластер. А последний кластер (6) - это крупные города и популярные города.